package demo16;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 电话号码的字母组合
 * https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/
 * 优化后
 */

class Solution {
    String[] map;
    List<String> ret = new ArrayList<>();
    int len;
    StringBuffer path = new StringBuffer();

    public List<String> letterCombinations(String digits) {
        map = new String[10];
        map[2] = "abc";
        map[3] = "def";
        map[4] = "ghi";
        map[5] = "jkl";
        map[6] = "mno";
        map[7] = "pqrs";
        map[8] = "tuv";
        map[9] = "wxyz";

        char[] chars = digits.toCharArray();
        len = chars.length;
        if (len == 0) return ret;
        dfs(chars, 0);
        return ret;
    }

    private void dfs(char[] digits, int pos) {
        if (path.length() == len) {
            ret.add(path.toString());
            return;
        }
        String  cur = map[digits[pos] - '0'];
        for (int i = 0; i < cur.length(); i++) {
            path.append(cur.charAt(i));
            dfs(digits,pos+1);
            path.deleteCharAt(path.length() - 1);
        }
    }
}

class Demo {
    public static void main(String[] args) {
        Solution solution = new Solution();
        List<String> list = solution.letterCombinations("23");
        for (String str : list) {
            System.out.println(str);
        }
    }
}